package leetcode._08_dynic;

import org.junit.Test;

/**
 * @author pppppp
 * @date 2022/4/7 20:56
 * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
 * 每步 可以删除任意一个字符串中的一个字符。
 *
 * 示例 1：
 * 输入: word1 = "sea", word2 = "eat"
 * 输出: 2
 * 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
 *
 * 示例  2:
 * 输入：word1 = "leetcode", word2 = "etco"
 * 输出：4
 *  
 * 提示：
 * 1 <= word1.length, word2.length <= 500
 * word1 和 word2 只包含小写英文字母
 */
public class _583_两个字符串的删除操作 {
    @Test
    public void T_0() {
        String[][] nums = {{"a","a"},{"sea","eat"},{"leetcode","etco"}};
        int[] ans = {0,2,4};
        for (int i = 0; i < nums.length; i++) {
            System.out.println(minDistance(nums[i][0],nums[i][1]) == ans[i]);
        }
    }
    public int minDistance(String word1, String word2) {
        if(word1.equals(word2)){
            return 0;
        }
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        char[] ch1 = word1.toCharArray();
        char[] ch2 = word2.toCharArray();
        for (int i = 1; i < word1.length()+1; i++) {
            for (int j = 1; j < word2.length()+1; j++) {
                if(ch1[i-1] == ch2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return word1.length() + word2.length() - 2*dp[word1.length()][word2.length()];
    }
}
